package leetcode.codetop.腾讯;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/11 15:30
 * @description：https://leetcode-cn.com/problems/3sum/
 */
public class 三数之和 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }


    /*
    // TTL
    class Solution {
        boolean vis[];
        public List<List<Integer>> threeSum(int[] nums) {
            this.vis = new boolean[nums.length];
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            backtrack(ans, new ArrayList<>(), nums, 0, 0);
            return ans;
        }

        private void backtrack(List<List<Integer>> ans, ArrayList<Integer> list, int[] nums, int curSum, int idx) {
            if (list.size() >= 3 || idx == nums.length) {
                if (list.size() == 3 && curSum == 0) {
                    ans.add(new ArrayList<>(list));
                }
                return;
            }
            for (int i = idx; i < nums.length; i++) {
                if (vis[i] || i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
                    list.add(nums[i]);
                    vis[i] = true;
                backtrack(ans, list, nums, curSum + nums[i], i + 1);
                vis[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
     */

    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            int n = nums.length;
            for (int first = 0; first < n; first++) {
                // 和上一个数一样
                if (first > 0 && nums[first] == nums[first - 1]) continue;
                int third = n - 1;
                int target = -nums[first];
                for (int second = first + 1; second < n; second++) {
                    if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                    while (second < third && nums[second] + nums[third] > target) {
                        third--;
                    }
                    if (third == second) break;
                    if (nums[second] + nums[third] == target) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        ans.add(list);
                    }
                }
            }
            return ans;
        }
    }
}
